package com.hl.algor_data_struct.sort;

import java.util.Arrays;

/**
 * Created by 31464 on 2021/10/26.
 * 快速排序：
 *         1）找到一个基准值pivot
 *         2）比pivot小的放在其左边，比pivot大的放在其右边
 *         3） 然后利用递归思想把基准值左右2边的数据进行排序
 */
public class QuickSort {

    private QuickSort(){}


    public static void main(String[] args) {
        //int[] arr={-9,78,0,23,-567,70};
        int[] arr={1,9,2,7,10,15,14,6,2};
        qucikSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void qucikSort(int[] arr,int left,int right){
        int l=left;//左边的指针
        int r=right;//右边的指针
        int mid=left+((right-left)>>1); //找到中间位置的索引


        int piovt=arr[mid];//中轴值，使用这个中轴值作为基准值（也可以使用数组中的最后一个值作为基准值）

        //让比pivot小的放到左边，比pivot大的放到右边
        while(l<r){
            //在pivot的左边一直找，找到大于等于pivot的值，才退出
            while(arr[l]<piovt){
                l+=1;//如果左边的值比中轴值要小，则左边的指针想右移动1位
            }
            //在pivot的右边一直找，找到小于于等于pivot的值，才退出
            while(arr[r]>piovt){
                r-=1;//如果左边的值比中轴值要大，则右边的指针想左移动1位
            }
            //如果l>=r 说明pivot的左右两边的值，已经按照左边是小于等于pivot值，右边是大于等于pivot值
            if(l>=r){
                break;
            }
            //交换数据
            SortConstants.swap(arr,l,r);

           //如果交换完成后，发现arr[l]==pivot ，则r--,
            if(arr[l] == piovt){
                r-=1;
            }
            //如果交换完成后，发现arr[r]==pivot ，则l++,
            if(arr[r] == piovt){
                l+=1;
            }
        }
        if(l==r){
            l+=1;r-=1;
        }
        //让左边进行排序
        if(left<r){
            qucikSort(arr,left,r);
        }
        //让右边进行排序
        if(right>l){
            qucikSort(arr,l,right);
        }
    }
}
